home *** CD-ROM | disk | FTP | other *** search
- From: RWilson@acorn.co.uk
- Subject: Dithering in general
- Date: 30 Jan 92 12:26:11 GMT
-
- As well as the deathless 'How to find the closest colour out of the RISC OS
- 256' (yes, *anyone* can use this code (especially Find256) - we'd like an
- acknowledgement, please!), here are some notes on dithering:
-
- (a) There are some text books that get the Floyd Steinberg error weights WRONG
- - the books say 2/8 3/8 and 3/8, but this (although cheaper to calculate)
- is not F-S, where the weights are 7/16, 5/16, 3/16 and 1/16.
-
- (b) ALL dithering algorithms look 'better' (less prone to regular artifact
- patterning) if the display is scanned serpentine (l-r one raster line,
- then r-l).
-
- (c) There are more expensive (and slightly better than F-S) schemes: see
- "Digital Halftoning" by Robert Ulichney published by the MIT Press, ISBN
- 0-262-21009-6.
-
- (d) ChangeFSI gets right. :-)
-
- (e) For god's sake, allow people access to the undithered data.
-
- --Roger
-
-
- From: RWilson@acorn.co.uk
- Subject: How to find the closest colour out of the RISC OS 256
- Date: 30 Jan 92 12:20:23 GMT
-
- ; MACRO ColErr
- ;
- ; Calculates an error value in $error corresponding to the difference
- ; between the two colours $col1 and $col2. Requires two temporary
- ; registers. All registers must be different. This routine requires
- ; 16 instructions, three of which are multiples plus for instructions
- ; for the error loading calculations. To speed up the multiplies
- ; the error value for each component is made positive.
- ;
- ; The error calculation is controlled by the following ``loading'' values.
- ; The basic component error calculation, given components c1 and c2 from
- ; $col1 and $col2, is:-
- ;
- ; e := ((c1-c2) ^ 2) * load
- ;
- ; Thus a higher ``load'' makes errors in the component more significant when
- ; the component value itself is small, however has little effect when the
- ; component value is large. Each loading must not exceed 65536/3 or the
- ; error calculation may overflow. If a loading exceeds 32768/3 the result may
- ; have the top bit set. The loadings are determined algorithmically by the
- ; following macros - this avoids having to do a real multiplication. The
- ; macros have the form:-
- ;
- ; XWeight $err, $sqr
- ;
- ; and calculate:-
- ;
- ; $err = $sqr * XLoad (for BLoad)
- ; $err += $sqr * XLoad (for GLoad, RLoad)
- ;
- ; $sqr may be overwritten. They are called in the order BLoad, GLoad
- ; RLoad, and are only called if the corresponding loading value is not
- ; 1.
- ;
- BLoad EQU 1
- MACRO
- $label BWeight $error, $sqr
- ASSERT 0
- MEND
-
- GLoad EQU 10
- MACRO
- $label GWeight $error, $sqr
- $label ADD $sqr, $sqr, $sqr, LSL #2
- ADD $error, $error, $sqr, LSL #1
- MEND
-
- RLoad EQU 3
- MACRO
- $label RWeight $error, $sqr
- $label ADD $sqr, $sqr, $sqr, LSL #1
- ADD $error, $error, $sqr
- MEND
-
- MACRO
- $label ColErr $error, $col1, $col2, $temp1, $temp2
-
- $label MOV $temp1, $col1, LSR #24
- SUBS $temp2, $temp1, $col2, LSR #24
- RSBLT $temp2, $temp2, #0
- [ BLoad /= 1
- MUL $temp1, $temp2, $temp2
- BWeight $error, $temp1
- |
- MUL $error, $temp2, $temp2
- ]
- MOV $temp2, #255
- AND $temp1, $temp2, $col1, LSR #16
- AND $temp2, $temp2, $col2, LSR #16
- SUBS $temp2, $temp1, $temp2
- RSBLT $temp2, $temp2, #0
- [ GLoad /= 1
- MUL $temp1, $temp2, $temp2
- GWeight $error, $temp1
- |
- MLA $error, $temp2, $temp2, $error
- ]
- MOV $temp2, #255
- AND $temp1, $temp2, $col1, LSR #8
- AND $temp2, $temp2, $col2, LSR #8
- SUBS $temp2, $temp1, $temp2
- RSBLT $temp2, $temp2, #0
- [ RLoad /= 1
- MUL $temp1, $temp2, $temp2
- RWeight $error, $temp1
- |
- MLA $error, $temp2, $temp2, $error
- ]
- MEND
- ;
- ; MACRO CompErr
- ;
- ; This macro also calculates an error value, however the second colour
- ; is specified as three separate r, g, b values. The registers containing
- ; these values can be the same, if desired. The registers should not be
- ; the same as any of the other registers. The calculation needs 16
- ; instructions, including three multiplies.
- ;
- MACRO
- $label CompErr $error, $col, $red, $green, $blue, $temp1, $temp2
-
- $label SUBS $temp2, $blue, $col, LSR #24
- RSBLT $temp2, $temp2, #0
- [ BLoad /= 1
- MUL $temp1, $temp2, $temp2
- BWeight $error, $temp1
- |
- MUL $error, $temp2, $temp2
- ]
- AND $temp1, $col, #&FF0000 ; green component, still shifted
- SUBS $temp2, $green, $temp1, LSR #16
- RSBLT $temp2, $temp2, #0 ; |green error|
- [ GLoad /= 1
- MUL $temp1, $temp2, $temp2
- GWeight $error, $temp1
- |
- MLA $error, $temp2, $temp2, $error
- ]
- AND $temp1, $col, #&FF00 ; red component, still shifted
- SUBS $temp2, $red, $temp1, LSR #8
- RSBLT $temp2, $temp2, #0 ; |red error|
- [ RLoad /= 1
- MUL $temp1, $temp2, $temp2
- RWeight $error, $temp1
- |
- MLA $error, $temp2, $temp2, $error
- ]
- MEND
- ;
- ; MACRO FindCol
- ;
- ; This macro finds the closest colour to the given r, g, b triple from
- ; an array of (word sized) RGB values (encoded BBGGRR00). The macro
- ; preserves the $red, $green and $blue values, exits with $error set
- ; to that of the found colour and $index set to the index of the entry. Again,
- ; all arguments must be different registers.
- ;
- MACRO
- $label FindCol $list, $listend, $red, $green, $blue, $error, $index, $ptr, $col, $temp1, $temp2, $temp3
-
- $label MOV $error, #&FFFFFFFF ; maximum error
- SUB $ptr, $list, #4 ; points to entry to last entry tried
- 0: LDR $col, [$ptr, #4]!
- CompErr $temp3, $col, $red, $green, $blue, $temp1, $temp2
- CMP $temp3, $error
- MOVLS $error, $temp3
- SUBLS $index, $list, $ptr ; index * 4
- CMP $ptr, $listend
- BLO 0b
- MOV $index, $index, LSR #2
- MEND
- ;
- ; MACRO Find256
- ;
- ; This macro finds the best matching colour for the *standard* ARM 256 entry palette - the
- ; one with the R/G/B/T (tint) bits. The algorithm returns a palette value encoded in the
- ; standard way (BGGRBRTT) in $col and the error in $error.
- ; All arguments must be different registers. The loop is about 44 instructions, including
- ; the normal three multiplies. The code goes round it four times, there is a further 12
- ; instruction overhead.
- ;
- ; The registers must all be different except for $red, $green and $blue, which can be
- ; the same if desired.
- ;
- ; The ARM palette entries are assumed to expand a 4 bit component to an 8 bit component
- ; using c<<4|c - this has been determined experimentally to give good results.
- ;
- MACRO
- $label Find256 $red, $green, $blue, $error, $col, $tint, $temp1, $temp2, $temp3, $pixel
-
- $label MOV $error, #&FFFFFFFF
- MOV $tint, #&30:SHL:23 ; tint bits unexpanded
-
- 0: RSB $temp1, $tint, #&20:SHL:23 ; overflow is not possible here
- SUB $temp2, $blue, $blue, LSR #4 ; effectively multiplication by 16/17
- ADDS $temp1, $temp1, $temp2, LSL #23
- ;
- ; At this point the top bits of $temp1 hold the best blue bit values given
- ; the current $tint tint bits, however the desired value may be >11tt or <00tt,
- ; in either case the top bit (bit 31) of $temp1 will be set, hence the N flag
- ; will be set in the PSR. We must distinguish overflow (>11tt) from a simple
- ; negative result (<00tt) and truncate both to the appropriate end of the
- ; scale. We have calculated (blue-tint+&22)<<23. The overflow (V) flag will
- ; ONLY be set for >11tt; the other possible results (in the range &FF<<23 to
- ; -&17<<23 are representable without overflow), so:-
- ;
- MOVVSS $temp1, #&7F000000 ; clears the N flag!
- MOVMI $temp1, #0
- ;
- ; Now extract the blue bits and reconstruct the real (expanded) blue value.
- ;
- AND $temp1, $temp1, #&60000000 ; two blue bits
- ADD $temp1, $temp1, $tint ; plus tint
- ADD $pixel, $temp1, $temp1, LSR #4 ; expand component bits - 8 bit blue value
- ;
- ; Calculate the error as above.
- ;
- SUBS $temp2, $blue, $pixel, LSR #23
- RSBLT $temp2, $temp2, #0 ; speeds up multiplication
- [ BLoad /= 1
- MUL $temp1, $temp2, $temp2
- BWeight $temp3, $temp1
- |
- MUL $temp3, $temp2, $temp2
- ]
- ;
- ; Repeat this for the green component, accumulating the error
- ;
- RSB $temp1, $tint, #&20:SHL:23
- SUB $temp2, $green, $green, LSR #4
- ADDS $temp1, $temp1, $temp2, LSL #23
- MOVVSS $temp1, #&7F000000
- MOVMI $temp1, #0
- ;
- AND $temp1, $temp1, #&60000000 ; two green bits
- ADD $temp1, $tint, $temp1 ; 4 bit green value
- ADD $temp1, $temp1, $temp1, LSR #4 ; expand component bits
- ORR $pixel, $pixel, $temp1, LSR #8 ; Accumulate bits in $pixel
- ;
- SUBS $temp2, $green, $temp1, LSR #23
- RSBLT $temp2, $temp2, #0
- [ GLoad /= 1
- MUL $temp1, $temp2, $temp2
- GWeight $temp3, $temp1
- |
- MLA $temp3, $temp2, $temp2, $temp3
- ]
- ;
- ; And the red component:-
- ;
- RSB $temp1, $tint, #&20:SHL:23
- SUB $temp2, $red, $red, LSR #4
- ADDS $temp1, $temp1, $temp2, LSL #23
- MOVVSS $temp1, #&7F000000
- MOVMI $temp1, #0
- ;
- AND $temp1, $temp1, #&60000000 ; two red bits
- ADD $temp1, $tint, $temp1 ; 4 bit red value
- ADD $temp1, $temp1, $temp1, LSR #4 ; expand component bits
- ORR $pixel, $pixel, $temp1, LSR #16 ; Accumulate bits in $pixel
- ;
- SUBS $temp2, $red, $temp1, LSR #23
- RSBLT $temp2, $temp2, #0
- [ RLoad /= 1
- MUL $temp1, $temp2, $temp2
- RWeight $temp3, $temp1
- |
- MLA $temp3, $temp2, $temp2, $temp3
- ]
- ;
- ; $temp3 contains the error for the ARM value in $pixel (actually this value
- ; is shifted right by 1 bit because of the LSL 23 above). Check the error
- ; and see if this is a better pixel.
- ;
- CMP $temp3, $error
- MOVLS $error, $temp3 ; LS, so selects lower tint in preference
- MOVLS $col, $pixel ; $col holds best match
- ;
- ; Try the next tint
- ;
- SUBS $tint, $tint, #&10:SHL:23
- BGE 0b
- ;
- ; $error is the error, and is directly comparable with the $error
- ; value from the other macros. $col to the ARM palette entry using
- ; the appropriate bit manipulations. The value is currently:-
- ;
- ; 0BBTT011 1GGTT011 1RRTT011 10000000
- ;
- ; We need to convert this to the form:-
- ;
- ; 76543210
- ; BGGRBRTT
- ;
- AND $temp1, $col, #&40000000 ; B (needs >> 23)
- MOV $temp2, $temp1, LSR #23
- AND $temp1, $col, #&600000 ; GG (needs >> 16)
- ORR $temp2, $temp2, $temp1, LSR #16
- AND $temp1, $col, #&4000 ; R (needs >> 10)
- ORR $temp2, $temp2, $temp1, LSR #10
- AND $temp1, $col, #&20000000 ; B (needs >> 26)
- ORR $temp2, $temp2, $temp1, LSR #26
- AND $temp1, $col, #&3800 ; RTT (needs >> 11)
- ORR $col, $temp2, $temp1, LSR #11
- MEND
-
-
-